package main

import (
	"fmt"
)

/*
有若干种贴纸，每张贴纸上有若干字母，可以撕碎贴纸，
求至少要多少张贴纸才能最终拼凑成str
*/
func minStep(rest string, arr [][26]int, dp map[string]int) int {
	if r, ok := dp[rest]; ok {
		return r
	}
	ans := int(^uint(0) >> 1)
	// 将 rest 映射为一维数组
	var restMap [26]int
	for i, c := range []byte(rest) {
		restMap[c - 'a']++
		fmt.Print(i)
	}

	for _, chars := range arr {
		first := GetFirst(restMap)
		if first == -1 {
			break
		}
		if chars[first] == 0 {
			continue
		}

		var buf []byte
		for i, c := range restMap {
			if c == 0 {
				continue
			}
			if c > chars[i] {
				restMap[i] = c - chars[i]
				for i = 0; i < (c -chars[i]); i++ {
					buf = append(buf, byte('a'+i))
				}
			} else {
				restMap[i] = 0
			}
		}
		cur := minStep(string(buf), arr, dp)
		ans = min(cur, ans)
	}

	if ans != int(^uint8(0) >> 1) {
		dp[rest] = ans
	} else {
		dp[rest] = -1
	}
	return dp[rest]+1
}

func GetFirst(arr [26]int) int {
	for i, v := range arr {
		if v != 0 {
			return i
		}
	}
	return -1
}

func min(a int, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}

func main() {
	arr := []string{"abd", "aabbc", "addc"}
	stringToOp := "abbbbbbddcc"
	// 将每种贴纸映射成二维切片
	stickers := make([][26]int, len(arr))
	for idx, str := range arr {
		for _, c := range []byte(str) {
			stickers[idx][c - 'a']++
		}
	}

	fmt.Println(stickers)
	dp := make(map[string]int, 0)
	dp[""] = 0
	res := minStep(stringToOp, stickers, dp)
	fmt.Println(res)
}